//
// Created by liushuai on 2021/1/17.
//

#include "zigzagLevelOrder.h"
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root)
{
    std::vector<std::vector<int>> result;
    if (!root)
        return result;
    else
    {
        std::stack<TreeNode*> odd;
        std::stack<TreeNode*> even;
        even.push(root);
        while (!even.empty() || !odd.empty())
        {
            int queue_size = even.size();
            std::vector<int> layers;
            for (int i = 0; i < queue_size; i++)
            {
                TreeNode* current = even.top();
                even.pop();
                layers.push_back(current->val);
                if (current->left)
                    odd.push(current->left);
                if (current->right)
                    odd.push(current->right);
            }
            if (!layers.empty())
            {
                result.push_back(layers);
                layers.clear();
            }
            int stack_size = odd.size();
            for (int i = 0; i < stack_size; i++)
            {
                TreeNode* current = odd.top();
                odd.pop();
                layers.push_back(current->val);
                if (current->right)
                    even.push(current->right);
                if (current->left)
                    even.push(current->left);
            }
            if (!layers.empty())
            {
                result.push_back(layers);
                layers.clear();
            }
        }
        return result;
    }
}
